#pragma once
#include <functional>
#include <string>
#include <cmath>

using namespace std;
template<class K, class V>
struct Node
{
	Node<K, V>(){ next = nullptr; }
	Node<K, V>(K key, V value)
	{
		this->key = key, this->value = value, this->next = nullptr;
	}
	K key;
	V value;
	Node<K, V> *next;
};

template<class K, class V>
class HashTable
{
	//class Iterator
	//{
	//public:
	//	typedef Iterator self_type;
	//	typedef Node<K, V> value_type;
	//	typedef Node<K, V>& reference;
	//	typedef Node<K, V>* pointer;
	//	typedef std::forward_iterator_tag iterator_category;
	//	typedef int difference_type;

	//	Iterator(pointer end) { ptr_ = nullptr; }
	//	Iterator(pointer *v, int size) : v(v), size(size)
	//	{
	//		index = 0;
	//		ptr_ = nullptr;
	//		do
	//		{
	//			if (v[index] != nullptr)
	//			{
	//				ptr_ = v[index];
	//				index++;
	//				break;
	//			}
	//			index++;
	//		} while (index < size);
	//	}

	//	self_type operator++()
	//	{
	//		self_type i = *this;

	//		if (ptr_ != nullptr)
	//		{
	//			ptr_ = ptr_->next;
	//		}


	//		if (ptr_ == nullptr)
	//		{
	//			if (index < size)
	//			{
	//				do
	//				{
	//					if (v[index] != nullptr)
	//					{
	//						ptr_ = v[index];
	//						index++;
	//						break;
	//					}
	//					index++;
	//				} while (index < size);
	//			}
	//		}
	//		return i;
	//	}
	//	//self_type operator++(int junk)
	//	//{
	//	//      ptr_ = ptr_->next; return *this;
	//	//}
	//	reference operator*() { return *ptr_; }
	//	pointer operator->() { return ptr_; }
	//	bool operator==(const self_type& rhs) { return ptr_ == rhs.ptr_; }
	//	bool operator!=(const self_type& rhs) 
	//	{ 
	//		return ptr_ != rhs.ptr_; 
	//	}
	//private:
	//	int index;
	//	pointer ptr_;
	//	pointer *v;
	//	int size;
	//};



	class Iterator
	{
	public:
		typedef Iterator self_type;
		typedef Node<K, V> value_type;
		typedef Node<K, V>& reference;
		typedef Node<K, V>* pointer;
		typedef std::forward_iterator_tag iterator_category;
		typedef int difference_type;

		Iterator(Node<K, V> *end) 
		{ 
			this->ptr_ = nullptr; 
		}
		Iterator(Node<K, V> **ptr, int size)  
		{
			this->ptr_ = ptr;
			this->list = *ptr;
			this->size_ = size;
		} //Constructor

		Iterator operator++() 
		{ 
			Iterator i = *this;
			
			while (count < size_ )
			{
				if (list != NULL)
				{
					if (list->next != nullptr)
					{
						list = list->next;
						return i;
					}
				}

				if (count >= size_ - 1)
				{
					ptr_ = nullptr;
					return i;
				}
				
				count++;
				ptr_ = ptr_++;
				list = *ptr_;
				if (*ptr_ != NULL)
					return i;
			}
		}
		//self_type operator++(int junk) { ptr_ = ptr_->next; return *this; }
		//reference operator*() { return *ptr_; }
		Node<K, V> *operator->() { return list; }
		//bool operator==(const self_type& rhs) { return ptr_ == rhs.ptr_; }
		bool operator!=(const self_type& rhs) 
		{ 
			return ptr_ != rhs.ptr_; 
		}

	protected:
		Node<K, V> *list;
		Node<K, V> **ptr_;
		int size_;
		int count = 0;
	};


private:
	Node<K, V> **arr;
	int size;
	hash<K> myHash;
public:

	HashTable()
	{
	}

	HashTable(int size)
	{
		this->size = size;
		arr = new Node<K, V>*[size];
		for (int i = 0; i < size; i++)
		{
			arr[i] = nullptr;
		}
	}

	~HashTable()
	{
		for (int i = 0; i < size; i++)
		{
			if (arr[i] != nullptr)
			{
				Node<K, V> *n = arr[i];
				Node<K, V> *d;
				while (n != nullptr)
				{
					d = n;
					n = n->next;
					delete d;
				}
			}
		}
		delete[] arr;
	}

	int calc_hash(K key)
	{
		int hash_key = myHash(key);
		int place = abs(hash_key) % size;
		return place;
	}

	void add(Node<K, V> *n)
	{
		int place = calc_hash(n->key);

		if (arr[place] == nullptr)
		{
			arr[place] = n;
		}
		else
		{
			n->next = arr[place];
			arr[place] = n;
		}
	}

	void Print()
	{
		cout << *arr << endl;
		for (int i = 0; i < size; i++)
		{
			Node<K, V> *n = arr[i];
			if (n != nullptr)
			{
				cout << i << " " << n->key << " " << n->value;
				cout << " " << n->next << endl;
				while (n->next != nullptr)
				{
					n = n->next;
					cout << i << " " << n->key << " " << n->value;
					cout << " " << n->next << endl;
				}
			}
			
		}
	}

	Node<K, V> *search(K key)
	{
		int place = calc_hash(key);
		if (arr[place] == nullptr)
			return nullptr;
		else
		{
			Node<K, V> *head = arr[place];
			if (head->key == key)
				return head;
			while (head->next != nullptr)
			{
				head = head->next;
				if (head->key == key)
					return head;
			}
		}
	}

	Iterator begin()
	{
		return Iterator(arr, size);
	}

	Iterator end()
	{
		//return Iterator(ptrptrnull, size);
		return Iterator(nullptr);
	}
};

